﻿//
//
//算法思路：
//
//1. 状态表⽰：
//对于这种「路径类」的问题，我们的状态表⽰⼀般有两种形式：
//i.从[i, j] 位置出发，巴拉巴拉；
//ii.从起始位置出发，到达[i, j] 位置，巴拉巴拉。
//这⾥选择第⼆种定义状态表⽰的⽅式：
//dp[i][j] 表⽰：⾛到[i, j] 位置处，⼀共有多少种⽅式。
//
//
//.状态转移⽅程：
//简单分析⼀下。如果 dp[i][j] 表⽰到达[i, j] 位置的⽅法数，那么到达[i, j] 位置之
//前的⼀⼩步，有两种情况：
//i.从[i, j] 位置的上⽅（[i - 1, j] 的位置）向下⾛⼀步，转移到[i, j] 位置；
//ii.从[i, j] 位置的左⽅（[i, j - 1] 的位置）向右⾛⼀步，转移到[i, j] 位置。
//由于我们要求的是有多少种⽅法，因此状态转移⽅程就呼之欲出了： dp[i][j] = dp[i - 1]
//[j] + dp[i][j - 1] 。
//
//
//3. 初始化：
//可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：
//i.辅助结点⾥⾯的值要「保证后续填表是正确的」；
//ii.「下标的映射关系」。
//在本题中，「添加⼀⾏」，并且「添加⼀列」后，只需将 dp[0][1] 的位置初始化为 1 即可。
//
//
//4. 填表顺序：
//根据「状态转移⽅程」的推导来看，填表的顺序就是「从上往下」填每⼀⾏，在填写每⼀⾏的时候
//「从左往右」。
//
//5. 返回值：
//根据「状态表⽰」，我们要返回 dp[m][n] 的值。


class Solution
{
public:
	int uniquePaths(int m, int n)
	{
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 创建⼀个 dp表
		dp[0][1] = 1; // 初始化

		// 填表
		for (int i = 1; i <= m; i++) // 从上往下
			for (int j = 1; j <= n; j++) // 从左往右
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		// 返回结果
		return dp[m][n];
	}
};